#ifndef FIVE_H_INCLUDED
#define FIVE_H_INCLUDED

#include "header.h"

int GetMiddle(int * ,int a, int b);
int Partition(int * array, int low, int high);

void swap(int &a, int &b)
{
    if (a != b)
    {
    a = a + b;
    b = a - b;
    a = a - b;
    }

}
void _swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int MinOfK(int *array, int length, int k)
{
    if (NULL == array || length < 1 || k < 1 || k > length)
        return -1;
    int subK = 0;

    do
    {
        if (subK < k - 1)
            subK = Partition(array, subK + 1, length - 1);
        else if (subK > k - 1)
            subK = Partition(array, 0, subK - 1);
        else
            break;
    }while (subK < length && subK > -1);

    return subK+1;
}


int Partition(int * array, int low, int high)
{
    if (low > high || low < 0 || high < 0)
        return -1;

    int mid = GetMiddle(array, low, high);
    cout << array[low] << array[mid] << endl;
    swap(array[low], array[mid]);
    cout << "after change "<< array[low] << array[mid] << endl;
//    _swap(&array[low], &array[mid]);

    int tmp = array[low];
    int head = low;
    int rear = high;

    while (head < rear)
    {
        while (head < rear && array[rear] > tmp)
            rear--;

        array[head] = array[rear];

        while (head < rear && array[head] <= tmp)
            head++;

        array[rear] = array[head];
    }
    array[head] = tmp;

    return head;
}

int GetMiddle(int *array, int low, int high)
{
    int mid = (low + high) / 2;


    if (array[low] < array[high])
    {
        if (array[low] > array[mid])
            mid = low;
        else if (array[high] < array[mid])
            mid = high;
    }else
    {
        if (array[high] > array[mid])
            mid = high;
        else if (array[low] < array[mid])
            mid = low;
    }
    return mid ;

}

void QuickSort(int *array, int low, int high)
{
    if(low < high)
    {
        int p = Partition(array, low, high);
        QuickSort(array, low, p - 1);
        QuickSort(array, p + 1, high);
    }
}

void TestFive ()
{
    int array[8] = {1,6,2,4,5,0,7,8};
        QuickSort(array, 0, 7);
//    int k = MinOfK(array, 8, 2);
    int i;
    for (i = 0; i < 8; i++)
        cout << array[i] << "  ";



    cout <<endl;
}

#endif // 5_FIVE_H_INCLUDED
